package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author zhangjy
 * @description 非递减子序列
 * <p>
 * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * <p>
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 * @date 2025/6/15 15:19
 */
public class FindSubsequences_491 {

    public static void main(String[] args) {

    }

    /**
     * dmsxl：递归回溯
     * <p>
     * 思路：去重逻辑与全排列 II、子集 II等都不同；因为该题要求在nums原有顺序上查找
     */
    public List<List<Integer>> ans2 = new ArrayList<>();
    public List<Integer> path2 = new ArrayList<>();
    public List<List<Integer>> findSubsequences2(int[] nums) {
        backtrack2(nums, 0);
        return ans2;
    }

    public void backtrack2(int[] nums, int startIndex) {
        if(path2.size() >= 2) {
            ans2.add(new ArrayList<>(path2));
        }
        HashSet<Integer> used = new HashSet<>();
        for(int i = startIndex; i < nums.length; i++){
            // 本层去重
            if (used.contains(nums[i]))
                continue;
            // path元素要满足非递减
            if(!path2.isEmpty() && path2.get(path2.size() -1 ) > nums[i])
                continue;
            // 记录元素
            used.add(nums[i]); // 表示该元素在本层已经使用过，本层后面不能再重复使用
            path2.add(nums[i]);
            // 向下递归
            backtrack2(nums, i + 1);
            // 回溯
            // 为什么不回溯used？——used记录的是记录本层元素是否重复使用，新的一层used都会重新定义（清空），所以要知道used只负责本层！
            path2.remove(path2.size() - 1);
        }
    }

    /**
     * 个解：错误！！！
     *
     * 错误原因：题意理解有误；原题是在nums原有顺序中，找所有非递减子序列，且子序列元素个数>=2；但是下列做法并没有在原有顺序上查找，而是转换为子集II处理。
     */
    public List<List<Integer>> ans = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public int[] used;
    public List<List<Integer>> findSubsequences(int[] nums) {
        // 转换为子集II，不过子集元素个数>=2；nums有重复元素，每个元素只能用一次
        // 先排序
        // 第一层for循环，给所有subsetSize下，查找目标组合

        // 1.返回值void；入参：nums、path、ans、used、subsetSize、startIndex
        // used用于树层去重
        // subsetSize，表示要查找子集的元素个数
        // startIndex=i+1，进入下层递归时，i及前面的元素都不重复判断，因为这里找的子集是组合
        // 2.递归终止条件
        // path收集的元素个数==subsetSize
        // 3.搜索过程
        // 树层去重
        // 记录
        // 向下递归
        // 回溯

        if (nums.length < 2) return ans;

        Arrays.sort(nums);
        //
        used = new int[nums.length];
        for (int i = 2; i <= nums.length; i++) {
            backtrack(nums, i, 0);
        }
        return ans;
    }

    public void backtrack(int[] nums, int subsetSize, int startIndex) {
        // 找到目标子集，收集并结束本层递归
        if (path.size() == subsetSize) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // 横向遍历
        for (int i = startIndex; i < nums.length; i++) {
            // 1.树层去重
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)
                continue;

            // 2.记录
            path.add(nums[i]);
            used[i] = 1;

            // 3.递归
            backtrack(nums, subsetSize, i + 1);

            // 4.回溯
            path.remove(path.size() - 1);
            used[i] = 0;
        }
    }

}
